package com.lsa.letcode.the105.btFromInorderPostorder;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.lsa.letcode.common.TreeNode;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 * 
 * Solution steps:
 * 1) Write out inorder and postorder seqs
 * 2) Notice that val = postorder[postStop] is indeed the root of the tree
 * 3) find idx - the index of the val in the inorder array
 * 4) notice that the traversals are like the following:
 *    [{traverse-inorder-left-subtree},{val}, {traverse-inorder-right-subtree}]
 *    [{traverse-postorder-left-subtree},{traverse-postorder-right-subtree},{val}]
 *    It is crucial that 
 *    	{traverse-inorder-left-subtree}.length = {traverse-postorder-left-subtree}.length
 *    	{traverse-inorder-right-subtree}.length = {traverse-postorder-right-subtree}.length
 *    since these are traversals of the same subtrees.
 * 5) So we design recursive buildTree returning the root of the tree given traversals (as offsets in the original array)
 * 
 * Notice to convert idx with diff=inStart - postStart when calc coords in the postOrder array.
 */
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
    	Map<Integer, Integer> value2InorderIndex = new HashMap<Integer, Integer>();
    	for (int i = 0; i < inorder.length; i++) {
    		value2InorderIndex.put(inorder[i], i);
		}
        return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, value2InorderIndex);
    }
    
    private TreeNode buildTree(int[] inorder, int inStart, int inStop,
			int[] postorder, int postStart, int postStop, Map<Integer, Integer> value2InorderIndex) {
		if (postStart > postStop || inStart > inStop) {
			return null;
		}
//		System.out.println(
//				Arrays.toString(Arrays.copyOfRange(inorder, inStart,
//						inStop + 1)) + " " + 
//						Arrays.toString(Arrays.copyOfRange(postorder,
//								postStart, postStop + 1)));
		int headVal = postorder[postStop];
		Integer i = value2InorderIndex.get(headVal);
		if (i == null) {
			throw new IllegalArgumentException("cannot find index from value");
		}
		
		TreeNode n = new TreeNode(headVal);
		int diff = inStart - postStart;
		n.left  = buildTree(inorder, inStart, i - 1, postorder, postStart, i - diff - 1, value2InorderIndex);
		n.right = buildTree(inorder, i + 1, inStop, postorder, i - diff, postStop - 1, value2InorderIndex);
		
		/*
		 * n.left = buildTree(preorder, preStart + 1, (i - diff) - (inStart - diff) + 1 - 1, inorder, inStart, i - inStart + 1 - 1);
		n.right = buildTree(preorder, i - diff + 1, preStop - (i - diff + 1) + 1, inorder, i + 1, inStop - (i + 1) + 1);
		 * */
    	return n;
    }
    
    public List<Integer> preorder(TreeNode n){
    	List<Integer> l = new ArrayList<Integer>();
    	preorderRec(n, l);
    	return l;
    }
    
    private void preorderRec(TreeNode n, List<Integer> l){
    	if (n != null) {
    		l.add(n.val);
    		preorderRec(n.left, l);
    		preorderRec(n.right, l);
    	}
    }
    
    public List<Integer> inorder(TreeNode n){
    	List<Integer> l = new ArrayList<Integer>();
    	inorderRec(n, l);
    	return l;
    }
    
    private void inorderRec(TreeNode n, List<Integer> l){
    	if (n != null) {
    		inorderRec(n.left, l);
    		l.add(n.val);
    		inorderRec(n.right, l);
    	}
    }
    
    public List<Integer> postorder(TreeNode n){
    	List<Integer> l = new ArrayList<Integer>();
    	 postorderRec(n, l);
    	return l;
    }
    
    private void postorderRec(TreeNode n, List<Integer> l){
    	if (n != null) {
    		postorderRec(n.left, l);
    		postorderRec(n.right, l);
    		l.add(n.val);
    	}
    }
}